Many tasks involve computing the inner product of a query vector with a set of database vectors to find database instances having the largest, or maximum, inner products (e.g., highest similarity). This is a Maximum Inner Product Search (MIPS) problem. But computation of the inner products via a linear scan requires O(nd) time and memory, which is prohibitive when the number of database vectors (n) and the dimensionality (d) is large.